package org.example.BinaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Right_view_of_binary_tree {
    public static ArrayList<Integer> arr = new ArrayList<>();
    static int rightDeep = 0;

    public static void main(String[] args) {
        //二叉树的右视图

        //给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode root = new TreeNode(0);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node5.left = node7;
        //System.out.println(getLeftDeep(root));
        //System.out.println(getRightDeep(root));
        get2(root,0);
        for (Integer i : arr) {
            System.out.print(i + " ");
        }
    }
    //BFS广度优先法
    public static void get(TreeNode root) {
        if (root == null) return;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode node = deque.poll();
                if (node.left!=null) deque.add(node.left);
                if (node.right!=null) deque.add(node.right);
                len--;
                if (len==0) arr.add(node.val);
            }
        }
    }
    //DFS深度优先法
    public static void get2(TreeNode root,int deep){
        if (root==null) return;
        //通过deep来区分每一层
        deep++;
        //在同一层中，从左向右添加，无值则添加，有值则覆盖，只要最右边的节点
        if (arr.size()<deep){
            arr.add(root.val);
        }else {
            arr.set(deep-1,root.val);
        }
        get2(root.left,deep);
        get2(root.right,deep);
    }
}
